Shortest Path Algorithm：Floyd

I use the same background, which I compose, as the previous blog.Absolutely, the meanning of inputs and outputs are the same.

Floyd

Floyd Algorithm is a Dynamic Programming Algorithm.It is more efficenct than Dijkstra and SPFA but it’s time complexity is higher which determinate Floyd Algorithm is not omnipotent due to his weakness in calculating with data of large scale.But I think Floyd Algorithm is superior to Dijkstra for its ablitity of dealing with negative weights.

We need：
an array dis to store the weight betweent two nodes.

Attentions：

1. we need to initial the array dis with datum given and find the lighter weight gratually;
2. there maybe two paths of different weight between two adjoined places;
3. the weight b to a is the same as a to b;
4. we see the node 0 is the super source and the weight between it and the node can be source is 0.

Core：
dis[i][k] = min{dis[i][k], dis[i][j] + dis[j][k]}

// Title：Dijkstra AC code
// Author： Call偶围城

#include <stdio.h>

#define MAX 1000
#define INF 1000000

int T, S, D;
int dis[MAX+1][MAX+1];
int total;

void floyd() {
    int i, j, k;
    int tmp;

    for (i = 0;i <= total;i++) {
        for (j = 0;j <= total;j++) {
            if (dis[i][j] == INF) 
                continue;

            for (k = 0;k <= total;k++) {
                tmp = dis[i][j] + dis[j][k];
                if (tmp < dis[i][k])
                    dis[i][k] = dis[k][i] = tmp;
            }
        }
    }
}

int main() {
    int i, j, k;
    int a, b, t;
    int min;

    while (scanf("%d%d%d", &T, &S, &D) != EOF) {
        for (i = 0;i <= MAX;i++)
            for (j = 0;j <= MAX;j++)
                dis[i][j] = INF;

        for (i = 0;i <= MAX;i++)
            dis[i][i] = 0;

        total = 0;
        for (i = 1;i <= T;i++) {
            scanf("%d%d%d", &a, &b, &t);
            if (a > total) total = a;
            if (b > total) total = b;
            if (dis[a][b] > t)
                dis[a][b] = dis[b][a] = t;
        }

        for (i = 0;i < S;i++) {
            scanf("%d", &k);
                dis[0][k] = dis[k][0] = 0;
        }

        floyd();

        min = INF;
        for (i = 0;i < D;i++) {
            scanf("%d", &k);
            if (min > dis[0][k])
                min = dis[0][k];
        }

        printf("%d\n", min);
    }

    return 0;
}